كيده: گريد 1هاي محاسباتي بهر هبرداري از منابع توزيع شده محاسباتي را
براي كاربردهايي كه به محاسبات پرحجم نياز دارند، فراهم م ينمايند. توسعه
برنام ههايي كه قادر به استفاده از اين امكانات باشند، يكي از چالش هاي پيش
روي محاسبات گريدي م يباشد. در اين مقاله، با ارائه يك مدل برنام هنويسي
موازي مبتني بر عام لهاي سيار بر روي گريد، تلاشي م يباشد كه به منظور حل
اين مشكل صورت پذيرفته است. ارائه اين مدل، كه با توسعه بستر گريدي به
و افزودن خواص و نيز فرامين راهبري عام لها به آن محقق گشته Alchemi نام
است، به كاربر اجازه م يدهد تا با استفاده از حركت عامل ها و ارتباط ميان آن ها،
برنامه موازي خود را توسعه دهد. اين ايده از نوآور يهاي اين مقاله محسوب
م يشود. به منظور ارزيابي اين سيستم، الگوريتم ضرب ماتري سها و نيز يافتن
مجموع هاي از نقاط در سيستم مزبور پياد هسازي شد هاند. Convex Hull
كليد واژه: گريد، محاسبات گريدي، محاسبات توزي عشده، عام لهاي سيار،
.Alchemi ، برنام هنويسي موازي، پردازش موازي، تحرك قوي
-1 مقدمه
1] و [ 2] استفاده هماهنگ و قابل اطمينان از ] گريدهاي محاسباتي 2
منابعي را كه از نظر جغرافيايي توزيع شد هاند، به منظور بهر هبرداري در
كاربردهايي مانند محاسبات پرحجم، آناليز داده هاي توزيع شده و تجسم از
راه دور 3 ميسر ساخت هاند. منابع در گريد نامتجانس م يباشند و اين منابع
ممكن است در حوزه هاي مديريتي متفاوت و متعددي قرار داشته باشند و
نيز نر مافزارهاي متفاوتي را اجرا نمايند. اين نر مافزارهاي متفاوت موجب
اعمال مقررات دسترسي متفاوت به آنها م يگردد. همچنين شبك ههايي كه
گر ههاي گريد را به هم وصل م ينمايند ويژگ يهاي كاركردي متنوعي
دارند. بنابراين با توجه به موارد فوق توسعه و اصلاح كاربردها به منظور
بهر هگيري از محي طهاي گريد به صورت چالشي در برابر محاسبات گريدي
در آمده است. هر يك از موارد فوق، انگيز هاي جهت انجام تحقيقات به
منظور ارائه يك مدل برنامه نويسي توزيع شده براي استفاده در محي طهاي
گريد فراهم م ينمايد. از جمله اين تحقيقات م يتوان به گون ههاي متعدد
،[ سيست مهاي شيءگرا [ 3] و [ 4]، ف نآور يهاي مبتني بر وب [ 1] و [ 5
8]، سيست مهاي گردش ] CORBA ،[ محي طهاي حل مسائل [ 6] و [ 7
كاري 4، سيستم هاي محاسباتي با توان بالا [ 9] و [ 10 ] و سيست مهاي
مبتني بر كامپايلرها [ 11 ] اشاره نمود.
در اين مقاله از عام لهاي سيار [ 12 ] تا [ 16 ]، به عنوان محمِلي براي
اين مقاله در تاريخ 29 دي ماه 1383 دريافت و در تاريخ 11 شهريور ماه 1385
بازنگري شد.
رو حالله مافي، بخش مهندسي كامپيوتر، دانشكده فني و مهندسي، دانشگاه فردوسي
مشهد، مشهد ، ايران.
حسين دلداري، بخش مهندسي كامپيوتر، دانشكده فني و مهندسي، دانشگاه فردوسي
.(email: hdeldari@yahoo.com) مشهد، مشهد ، ايران
1. Grid
2. Computational Grid
3. Remote Visualization
4. Workflow
برنام هنويسي موازي بر روي گريد استفاده شده است. قابليت مهاجرتِ
خودمختار عام لها امكان استفاده از آ نها را در محيط شبك هاي كه همواره
در حال تغيير است، فراهم م ينمايد. حم لپذيري كه از خواص ذاتي
عام لها مي باشد (به علت پياد هسازي بر روي بسترهاي مستقل از سكو
امكان مديريت شفاف توزيع وظايف در محيطي ،(.NET و Java مانند
نامتجانس را فراهم نموده است. همچنين م يتوان از عام لها در تعديل بار
كاري گر ههاي شبكه نيز استفاده نمود. از مزاياي اصلي استفاده از
عام لهاي سيار در برنام هنويسي موازي، نسبت به استفاده از انتقال پيام،
حركت كد به سوي داد هها در كاربردهايي است كه در آن ها حجم
داد ههاي مبادله شونده قابل توجه م يباشد. به همين علت، عام لهاي سيار
گزين هاي مناسب براي برنام هنويسي موازي، مي باشند. همچنين برنامه
توزي عشد هاي كه با استفاده از مدل برنامه نويسي عام لگرا نوشته شده باشد،
خواناتر است و نيز مطابقت بيشتري با نگارش سِري آن دارد.
يكي از مشكلات برنامه نويسي موازي در محي طهاي انتقال پيام، كار با
ساختارهاي داد هاي م يباشد كه داراي اشار هگر هستند (مانند درخ تها).
زيرا در هنگام انتقال اين نوع ساختار داد هها بين پرداز شها ساختار داده
بايد به صورت خطي درآيد. ولي با استفاده از عامل هاي سيار به اين كار
نيازي نيست زيرا عام لهاي سيار كدي م يباشند كه به سمت داده حركت
م ينمايند. در نتيجه لازم نيست كه ساختار داده به صورت خطي درآيد.
از سوي ديگر، بسترهاي گريد كنوني، امكان اشتراك منابع محاسباتي
را در وضعيتي مديري تشونده و قابل اطمينان، براي كامپيوترهاي شخصي
و نيز ايستگا ههاي كاري فراهم نمود هاند. اين بسترها، محدوديت اتصال
را از بين برده اند و با ايجاد توپولوژي LAN كامپيوترها از طريق يك
سلسله مراتبي، حوزه بكارگيري از منابع را به شبك ههاي بسيار بزرگتري،
17 ] و ] Messengers گسترش داد هاند (سيست مهاي عام لگرايي از قبيل
18 ] با اين محدوديت مواجه مي باشند). همچنين اين بسترها، با اِعمال ]
ملاحظات امنيتي، محيطي قابل اعتماد را در اختيار كاربران قرار م يدهند.
در اين مقاله، با انگيزه استفاده از امكانات گريد و نيز بهره مندي از
مزاياي عامل هاي سيار در ساخت برنامه هاي موازي از بستر گريدي با نام
19 ] كه سيستمي ك محجم، پرقابليت و با منبع باز م يباشد، ] Alchemi
از قابليت تحرك ضعيف 5 Alchemi استفاده شده است. بستر گريد
عام لها [ 20 ] پشتيباني م يكند. قابليت تحرك ضعيف اشياء، يعني زماني
كه يك شيء انتقال م ييابد (شيء به صورت نخ 6 پياد هسازي شده است)،
فقط م يتوان آن را از نقطه آغازش اجرا نمود. در صورتي كه در
برنام هنويسي موازي توسط عام لهاي سيار، به قابليت تحرك قوي 7 نياز
است. قابليت تحرك را قوي گويند اگر امكان ادامه اجراي اين نخ از
نقط هاي كه قبلاً تا آنجا اجرا شده است، ميسر باشد. عيب ديگر اين
سيستم، اين است كه امكان ارتباط ميان نخ ها در حين اجرا وجود ندارد. در
را فقط در مواردي م يتوان استفاده نمود كه Alchemi نتيجه، سيستم
5. Weak Mobility
6. Thread
7. Strong Mobility
برنامه نويسي موازي مبتني بر عام لهاي سيار بر روي گريد
روحالله مافي و حسين دلداري
www.SID.ir
dibaketab.com
نشريه مهندسي برق و مهندسي كامپيوتر ايران، سال 5، شماره 2، تابستان 1386
70
كاربرد موازي به قطعات كاملاً مجزا از هم قابل تجزيه باشد. بنابراين
از اين سيستم براي مواز يسازي ساير الگوهاي الگوريتمي نم يتوان
استفاده نمود.
با توجه به نكات فوق، در اين تحقيق، تغييرات بنياديني در سيستم
داده شده است. يعني امكان ارتباط ميا ننخي 1 و قابليت تحرك Alchemi
قوي به آن افزوده گشته است. با ايجاد قابليت اجراي فرامين راهبري 2
مربوط به عامل ها در اين سيستم، امكان برنام هنويسي عام لگرا فراهم
شده است.
سيستم جديد را، كه پس از اين تغييرات داراي قابلي تهاي افزو نتري
ناميد هايم. همچنين آزمايشاتي كه به منظور ارزيابي Alchemi+ ، م يباشد
كارآيي سيستم فوق صورت گرفته است، بيانگر رسيدن به كارآيي بالاتر
كه بر روي گريد MPI نسخ هاي از ) MPICH-G نسبت به سيستم 2
گلوباس 3 قابل نصب است) م يباشد.
در ادامه اين مقاله نگاهي گذرا به پيش زمين ههاي مباحث به كار گرفته
شده در اين نوشتار خواهيم داشت و سپس با ذكر تغييرات اعما لشده در
به ارزيابي كارآيي اين سيستم توسط دو الگوريتم ،Alchemi سيستم
مجموع هاي از نقاط خواهيم Convex Hull ضرب ماتري سها و يافتن
پرداخت. در انتها با نتيجه گيري از كارهاي انجا مشده به كارهايي كه در
آينده در راستاي اين تحقيق قابل انجام م يباشد اشاره خواهد شد.
-2 پي شزمينه
در اين بخش به بيان پي شزمينه مختصري در مورد گريد، نقش
و نيز سيستم Messengers عام لها در محاسبات گريدي، سيستم
خواهيم پرداخت. سپس مختصري درباره مدل انتقال پيام Alchemi
MPI و پياد هسازي آن در گريد بحث خواهد شد. اگرچه MPI
پي شزمين هاي بر اين تحقيق نم يباشد ولي به علت اينكه زمان اجراي
در MPI الگوريتم در اين سيستم با زمان اجراي همان الگوريتم تحت
گريد و نيز در سيستم انتقال پيام مقايسه شده است تا معياري براي
ارزيابي كارآيي وجود داشته باشد. بنابراين مختصري درباره آن توضيح داده
شده است.
1 گريد -2
هدف از محاسبات گريدي، ترسيم يك كامپيوتر مجازي بزرگ،
قدرتمند و خودمديريت شونده است، كه از اجتماع نامتقارني از سيست مهايي
كه هر يك، تركيبي از منابع را به اشتراك گذاشته اند، تشكيل شده است.
در دهه گذشته، استانداردسازي ارتباطات ميان سيستم هاي مختلف و
نامتقارن موجب پديدآمدن اينترنت شد و اكنون استانداردسازي اشتراك
منابع با استفاده از پهناي باند بالا ميان اين سيست مها، بزرگترين قدم در
محاسبات گريدي است. گريد توسط يان فاستر 4 از بنيا نگذاران پروژه
گلوباس و مبدِع اصطلاح گريد، به صورت زير تشريح شده است:
گريد و فناوري هاي مرتبط در صدد تحقق اشتراك منابع به صورت
كنتر لشده و انعطا فپذير در انداز ههاي بالا م يباشند. اين مهم به وسيله
ساخت و توسعه پروتكل ها، سروي سها و بست ههاي توسعه نر مافزار ميسر
.[ م يشود [ 1
1. Inter-Thread Communication
2. Navigational Commands
3. Globus Toolkit
4. Ian T. Foster
[22] I-WAY 21 ] و ] FAFNER در دهه گذشته پروژه هايي مانند
كه تحت عنوان ابرمحاسب هگري 5 انجام شدند، زمينه را براي پروژه ها و
بسترهاي گريد كنوني فراهم آوردند. در حال حاضر بسترهاي گريد فراواني
توسعه يافت هاند كه هر يك بر جنبه خاصي از محاسبات گريدي متمركز
شد هاند. گلوباس [ 23 ] كه از مشهورترين بسترهاي گريد م يباشد بر پايه
بنا شده است. (OGSA) استاندارد معماري باز سروي سهاي گريد 6
2 عام لها و محاسبات گريدي -2
تلا شهاي زيادي به منظور استفاده از عام لها در جنبه هاي مختلفي از
محاسبات گريدي صورت گرفته است. بخش عمد هاي از اين تلا شها
[ معطوف به ساخت گريدي با استفاده از عام لهاي سيار م يباشد. در [ 24
معماري چهارلاي هاي به منظور ساخت يك گريد محاسباتي ارائه شده است
كه در لايه زيرين خود از عامل هاي سيار به عنوان محملي براي اشتراك
منابع محاسباتي كامپيوترها استفاده م يكند. فعاليت مشابهي در [ 25 ]، به
منظور ساخت گريد بر پايه عام لها انجام شده است. در اين كار، عام لها
از طريق يك "فضاي چندتايي 7" با يكديگر در ارتباط م يباشند.
ماشي نهايي كه منابعي را در اختيار گريد م يگذارند، به صورت يك عامل
JXTA 26 ] بستري بر روي 8 ] A-Peer سيار بازنمايي م يشوند. در پروژه
به منظور محاسبات همتا- به- همتا 9 ،IBM Aglets و با استفاده از سيستم
فراهم شده است. در [ 27 ] به منظور حل مشكل بازنمايي كاربران سيار (از
جمله برنامه هايي كه بر روي تلفن همراه و يا كامپيوترهاي همراه اجرا
م يشوند) از عامل هاي سيار در نماي هسازي 10 آنها بر روي بستر گريدي
استاندارد (گلوباس)، استفاده شده است.
از عامل هاي سيار در ساخت گريدهاي خا صمنظوره 11 استفاده م يشود.
28 ] مثالي از اين نوع است كه مورد استفاده بيولوژيس تها قرار ] MyGrid
م يگيرد. در اين پروژه، عام لها در محاوره با كاربر (به منظور
سفارش يكردن داد هها) و نيز در مذاكراتي كه براي رسيدن به "سطح
انجام م يشود، به كار گرفته شد هاند. در پروژه "(SLA) سرويس توافقي 12
مشابهي [ 29 ]، از گريدي بر پايه عام لها در مديريت شبكه هاي مخابراتي
و كامپيوتري استفاده شده است.
در تلا شهاي جداگانه ديگري، از عام لها به منظور بهبود كارآيي
نر مافزارهاي موازي و توزي عشده [ 30 ]، در بهين هسازي جستجو در
31 ]، مديريت منابع در گريد [ 29 ]، بهبود تحمل ] گريدهاي داد هاي 13
[ خرابي در گريد [ 32 ] و نيز مديريت سروي سها در گريد [ 33 ] و [ 34
استفاده شده است.
در مقاله حاضر، به شيو هاي متفاوت از تحقيقات فو قالذكر، از عامل هاي
سيار به منظور برنام هنويسي بر روي بستر گريد استفاده شده است. اين
رويكرد موجب شده است كه مزاياي استفاده از عامل ها در برنام هنويسي
موازي و نيز به كارگيري بستر گريد كه فراه مكننده منابع محاسباتي
فراواني است، در اختيار كاربرد موازي قرار گيرد.
5. Metacomputing
6. Open Grid Services Architecture
7. Tuple Space
8. A Sun Product for Peer-to-Peer Computing Stands for JuXTApose
9. Peer-to-Peer Computing
10. Profiling
11. Special Purpose
12. Service Level Agreement
13. Data Grid
www.SID.ir
dibaketab.com
مافي و دلداري: برنام هنويسي موازي مبتني بر عامل هاي سيار بر روي گريد
71
Messengers 3 سيستم -2
از مه مترين سيستم هايي كه از عام لهاي سيار در ساخت برنام ههاي
Messengers موازي هم همنظوره استفاده نمود هاند، م يتوان به سيستم
توسعه يافته است، اشاره نمود. UCI 17 ] و [ 35 ] تا [ 37 ] كه در دانشگاه ]
در اين سيستم، كاربردها با استفاده از مجموع هاي از ن خها ايجاد
ناميده م يشوند. Messenger م يگردد. اين ن خها قابليت مهاجرت داشته و
مانند تمامي سيست مهايي كه از قابليت تحرك قوي پشتيباني م يكنند، هر
م يتواند اجراي خود را متوقف ساخته، مقادير متغيرهاي ،Messenger
خود را درون خود ذخيره كرده و به گره ديگري حركت نمايد. سپس در آن
گره حالت خود را بازيابي م يكند و اجرا را از محل قبلي ادامه م يدهد. در
انجام م يشود. hop() اين سيستم اعمال فو قالذكر توسط دستور
در زبان معرف يشده توسط اين سيستم، دو نوع متغير وجود دارد:
متغيرهاي عامل و متغيرهاي گره. متغيرهاي عامل متعلق به هر عامل
بوده و در ضمن حركت عامل در شبكه، به همراه آن حمل م يشود. ولي
متغيرهاي گره براي هر گره تعريف شده و توسط تمامي
هايي كه بر روي آن گره خاص قرار دارند، قابل دسترسي Messenger
م يباشد. در نتيجه، متغيرهاي عامل م يتوانند به منظور حمل داده ميان
گر هها مورد استفاده قرار گيرند، در حالي كه متغيرهاي گره، توانايي مقادير
زيادي داده را بر روي خود داشته و مي توانند در ارتباطات ميا ننخي مورد
م يتواند با استفاده از فرمان Messenger بهر هبرداري قرار گيرند. هر
عام لهاي ديگر را اجرا نمايد. همگامي ميان عامل ها توسط inject()
م يتوان يك عامل signalEvent() رويداد 1ها صورت م يپذيرد. با فرمان
يك عامل را م يتوان waitEvent() را بيدار كرد و با استفاده از فرمان
بلوكه نمود. بنابراين اين فرما نها مفاهيم بلوكه شدن 2 و بيدارشدن 3 را
پياد هسازي مي كنند. به جهت اينكه رويدادها محلي هستند، همگا مسازي
نيز در سطح يك گره انجام م يشود و عام لها مجاز نيستند كه به
داد ههاي يكديگر از راه دور دسترسي داشته باشند. براي انتقال كنترل از
و يا hop() يك عامل به عامل ديگر، صراحتاً بايستي از دستورات
" استفاده نمود. اين ويژگي "زما نبندي غير قبض هاي 4 inject()
ناميده م يشود.
از مفهوم عام لهاي سيار، بر خلاف بسياري Messengers در سيستم
هستند، به Java از سيست مهاي عام لگراي ديگر كه عمدتاً مبتني بر
عنوان يك مدل برنام هنويسي موازي استفاده شده است. قابليت تحرك
به اين معني است كه محاسبات، و ،Messengers قوي موجود در سيستم
نه كُد، در طول شبكه حركت م يكند. به همين منظور در تبديل اسكريپت
به كد اجرايي، از كامپايلي دومرحل هاي استفاده شده است. Messengers
در محل عبارات راهبري، به توابع ،Messengers در مرحله اول برنامه
شكسته م يشود. اجراي اين توابع توسط يك C كوچكتري به زبان
.[ شمارنده برنامه منطقي با نام "اشار هگر به تابع بعدي" دنبال م يشود [ 35
(اشار هگر در نام شمارنده برنامه با اغماض به كار رفته و به منظور اشاره به
فضاي آدرس مشخصي نم يباشد، اين شمارنده داراي ساختمان داده
ويژ هاي مي باشد و براي ذخير هسازي دستور اجرايي بعدي به كار م يرود)
اين شمارنده برنامه منطقي و نيز متغيرهاي عامل، از طريق انتقال پيام با
استفاده از سوكت ها، بين گر هها رد و بدل م يشوند. سربار اين عمل (هر
1. Event
2. Blocking
3. Wake up
4. Non-Preemptive Scheduling
شامل اطلاعات داخلي در مورد ،(MCB) 5Messenger بلوك كنترلي
عامل است) براي هر عامل، حدود 200 بايت م يباشد. در مرحله دوم؛
به زبان ماشين ترجمه شده و به صورت كتابخانه هايي به منظور C توابع
اجرا، بر روي گر ههاي شبكه بارگذاري م يشوند.
38 ] سيستم پيشنهادي ] Jmessengers در تحقيق ديگري با نام
بر روي جاوا پياد هسازي شده است كه محصول به دست Messengers
ضعيف تر م يباشد ولي از Messengers آمده از نظر كارآيي نسبت به
قابليت حم لپذيري بيشتري برخوردار است.
در اين مقاله نيز به منظور افزودن امكانات برنام هنويسي موازي مبتني
از مدل پيشنهادي (Alchemi بر عام لهاي سيار بر روي گريد (سيستم
استفاده شده است با اين تفاوت كه سيستم توسع هيافته در Messengers
از مزايايي از جمله Messengers نسبت به (Alchemi+) اين مقاله
مقيا سپذيري 6 بهتر، امنيت بالاتر و پي شپردازش سب كتر برخوردار است.
Alchemi 4 سيستم -2
يكي از سيست مهايي كه محاسبات گريدي، را بر روي شبك هاي از
[ 19 ] و [ 39 ] Alchemi كامپيوترهاي شخصي فراهم م ينمايد، سيستم
م يباشد. اين سيستم برخلاف اغلب زيرساختارهاي گريد، بر روي
پياد هسازي شده است. اين .NET و با استفاده از چارچوب Windows
سيستم، عل يرغم حجم كم، با برخورداري از معماري و مؤلف ههاي كارآمد،
بستر انعطاف پذير و مستحكمي را براي محاسبات گريدي فراهم
آورده است.
در اين سيستم، دو مدل نخ گريدي و كار گريدي، كه به ترتيب در
نوشتن برنام ههاي گريدي و اجراي برنام ههاي از قبل نوشته شده بر روي
گريد كاربرد دارد پيشنهاد شده است. همچنين در اين سيستم امكاني براي
تعامل با ديگر ميان افرازهاي گريدي كه بر اساس خدمات وب كار
م يكنند، نيز در نظر گرفته شده است. يكي از معايب اين سيستم، عدم
امكان ارتباط ميان ن خهاي در حين اجرا م يباشد. در نتيجه اين نقصان،
تنها در مواردي كه كاربرد موازي به قطعات كاملاً از Alchemi سيستم
هم مجزا تجزيه شود، كاربرد دارد و برنام هنويسي با آن در ديگر الگوهاي
ارتباطي مقدور نيست.
5 انتقال پيام -2
يك روش برنام هنويسي موازي رايج براي سيست مهاي با حافظه
توزي عشده روش انتقال پيام م يباشد. در اين روش به زبا نهاي رايج
برنام هنويسي در كامپيوترهاي سري تعدادي فرمان كتابخان هاي اضافه
م يگردد. زبان حاصل امكان برنامه نويسي موازي را فراهم م يآورد. اين
كتابخان هها شامل روي ههايي براي مقداردهي اوليه و پيكربندي محيط
پيا مها مثل ارسال و دريافت بست ههاي داده م يباشند. در حال حاضر دو
مورد استفاده قرار م يگيرد كه PVM و MPI سيستم انتقال پيام رايج
پي شزمين هاي بر MPI پياد هساز يهاي مختلفي از آنها وجود دارد. گرچه
اين تحقيق نم يباشد ولي به علت اينكه نتايج عملي اجراي الگوريت مهاي
با نتايج Alchemi+ در سيستم Convex hull ضرب ماتريس و نيز
در محيط گريد مقايسه شده MPI و نيز MPI همين الگوريت مها در محيط
است، بنابراين مبادرت به توضيح مختصري در مورد آنها م يگردد. از
كارهايي كه در زمينه محاسبات موازي با استفاده از بسترهاي گريد صورت
5. Messenger Control Block
6. Scalability
www.SID.ir
dibaketab.com
نشريه مهندسي برق و مهندسي كامپيوتر ايران، سال 5، شماره 2، تابستان 1386
72
.GMONITOR جدول 1: فهرست اعضاء كلاس
قفلي از يك شيء را به دست مي آورد. اين عمل م يتواند
به عنوان آغاز يك ناحيه بحراني تلقي گردد. هيچ نخ
ديگري نم يتواند وارد اين ناحيه بحراني شود، مگر آنكه
دستورالعم لهايي در ناحيه بحراني اجرا كند كه از شيء
قف لشده ديگري استفاده مي كند.
Enter,
TryEnter
قفل يك شيء را به منظور اجازه دسترسي و قف لكردن به
ديگر ن خها، آزاد م ينمايد. نخ فراخواننده اين دستور تا
زماني كه نخ ديگر يك شيء مورد نظر دسترسي دارد،
منتظر مي ماند.
Wait
سيگنالي به يك يا چند نخ در حال انتظار ارسال مي كند.
اين سيگنال تغيير در وضعيت شيء قف لشده و نيز آمادگي
براي آزادكردن قفل توسط ايجادكننده قفل را به نخ در
حال انتظار اعلان م ينمايد. نخ در حال انتظار در صف
قرار گرفته، تا بتواند در (object's ready queue) آماده
زمان ممكن قفلي بر روي شيء به دست آورد.
Pulse
(signal),
PulseAll
قفل يك شيء را آزاد مي كند. اين عمل به عنوان نشانه اي
بر انتهاي ناحيه بحراني كه توسط شيء قفل شده، ايجاد
شده بود، تلقي م يگردد.
Exit
اشاره نمود. در اين تحقيق ضمن MPICH-G گرفته است م يتوان به 2
ارائه معماري به كار گرفته شده در ساخت اين ميا نافزار امكان اجراي
MPIAB . در محيط گريد ميسر است MPI برنام ههاي نوشت هشده تحت
م يباشد كه از عام لها در جاوا MPI 40 ] يك مدل مبتني بر عامل از ]
استفاده نموده است. هدف اين سيستم MPI براي پياد هسازي توابع
بهر هگيري از تكنولوژي جاوا و عام لها براي افزايش كارآيي ارتباطات و
نيز همگامي بين گر هها بر روي شبكه م يباشد.
محاسبات توزي عشده مبتني بر :ALCHEMI+ -3
عام لها بر روي گريد
2 و برتر يهاي - با توجه به نكات برشمرد هشده در بخش 2
برنام هنويسي موازي عام لگرا نسبت به برنام هنويسي موازي با استفاده از
داده Alchemi انتقال پيام، در اين تحقيق تغييرات گسترد هاي در سيستم
شده است. با استفاده از اين تغييرات امكان برنام هنويسي موازي مبتني بر
عام لها بر روي گريد فراهم شده است. از جمله امكاناتي كه در اين
افزوده شده است م يتوان از ايجاد ارتباط Alchemi تحقيق به سيستم
ميا ننخي و نيز ايجاد تحرك قوي نام برد.
1 ايجاد ارتباط ميا ننخي -3
(GThread امكان ارتباط ميان ن خها (اشياء كلاس ،Alchemi در
پياد هسازي نشده است. به جهت نياز به ارتباط ميا ننخي در برنام هنويسي
مبتني بر عام لهاي سيار (در كاربردهايي مانند همگا مسازي) كلاس
پياد هسازي .NET در چارچوب Monitor مشابه كلاس ،GMonitor
بر روي ن خهايي كه بر GMonitor شده است، با اين تفاوت كه كلاس
روي كامپيوترهاي مختلف قرار دارند، عمل مي كند. در جدول 1 فهرستي
ارائه شده است. GMonitor از متدهاي كلاس
در اين سيستم با ايجاد يك قفل بر روي يك شيء با متد
با استفاده از واسط هر عامل (كه به صورت نخ ،GMonitor.Enter
پياد هسازي مي شود) اطلاعات قفل و شيء قف لشده، به مدير سيستم
منتقل م يشود. در گره مدير سيستم، همواره فهرستي از قفل هاي
اِعما لشده در سيستم كنوني موجود است. از اين پس هرگاه عامل ديگري
بخواهد با اين عامل همگام گردد و يا اطلاعاتي را از اين عامل دريافت
GMonitor.EnterTry نمايد، از شيء مذكور استفاده م ينمايد و با متد
آن را وارسي م ينمايد. اگر قفلي بر روي آن عامل وجود داشته باشد تا
زماني كه آن قفل آزاد نگردد، عامل درخواس تكننده هماهنگي معلق
م يماند (در فهرست قفل ها، شناسه عامل ايجادكننده قفل و عام لهايي كه
بر روي آن متوقف شد هاند، نيز نگهداري م يشود).
2 پياد هسازي قابليت تحرك قوي -3
عام لها داراي تحرك قوي م يباشند. در Alchemi+ در سيستم
پياد هسازي قابليت تحرك قوي براي عام لها (كه به صورت نخ پياد هسازي
م يشوند) كد داراي ويژگي قابليت تحرك قوي به كد داراي ويژگي
تحرك ضعيف ترجمه م يگردد. در اين مقاله مقصد ترجمه، كلاس
بوده و داراي Alchemi است كه از كلاس هاي سيستم GThread
توانايي تحرك ضعيف م يباشد.
به يك كلاس دروني 1 (GAgent) هر متد، در كلاس اصلي عامل
مشخص م يشود) كه [Serializable] با نماد C# كه در ) Serializable
حاوي ركورد فعا لسازي آن متد است، ترجمه م يشود. متغيرهاي محلي،
پارامترهاي متد و شمارنده برنامه به فيلدهاي اين كلاس تبديل مي شوند.
است، كه در برگيرنده بدنه اصلي متد run() كلاس دروني شامل يك متد
م يباشد. كلاس دروني عاملي كه قابليت تحرك قوي دارد، شامل آراي هاي
از ركوردهاي فعال سازي شيءهاي كلاس اصلي است، كه به صورت يك
جدول مجازي از متدها، عمل م يكند.
اجراي عبارات و نيز تغيير شمارنده برنامه، بايستي به صورت اتميك
انجام شوند، تا به عامل اجازه داده شود از مكاني به مكان ديگر، بدون از
دس تدادن اطلاعات، حركت نمايد. بدين علت كد اصلي به گون هاي ترجمه
م يشود كه امكان ذخيره وضعيت عامل در هر لحظه ميسر باشد. اين عمل
به نحوي انجام م يشود كه معاني عبارات حفظ شود و منطق برنامه نيز
C# تغيير نكند. وجود قوانين ترجمه متفاوت براي عبارات مختلف در
الزامي است.
موجب حركت يك عامل به مقصد جديدش خواهد شد. ،Go() متد
مشخص شده است، وضعيت [Serializable] لاي هاي كه توسط ويژگي
ايستاي عامل را ذخيره م ينمايد. اين لايه پس از رسيدن به مقصد، اشيائي
ساخته و آ نها را به وضعيت اجراي قبل يشان باز GThread از كلاس
م يگرداند. عملگرهايي كه اجراي آنها تا زمان معيني به طول خواهد
متوقف شده و زمان باقيمانده از اجراي (Thread.Sleep() انجاميد، (مانند
آنها، قبل از حركت ذخيره مي شود. در پياد هسازي انجا مشده از قابليت
ContextInfo و GAgent و دو كلاس IAgent تحرك قوي، واسط
وجود دارند.
IAgent 1-2-3 واسط
را IAgent هر عامل سيار بايستي (مستقيم و يا غير مستقيم) واسط
يك واسط نشانگر 2 است كه لزوم ،IAgent پياد هسازي كند. واسط
پياد هسازي توابع اين كلاس را توسط برنام هنويس به كامپايلر (و يا
عامل را به مقصد كه توسط ،Go() پي شپردازشگر) گوشزد م يكند. تابع
IAgent معين م يشود، حركت م يدهد. واسط GNode متغيري از كلاس
1. Inner
2. Marker Interface
www.SID.ir
dibaketab.com
مافي و دلداري: برنام هنويسي موازي مبتني بر عامل هاي سيار بر روي گريد
73
.GAGENT جدول 2: فهرست اعضاء كلاس
agentManager Alchemi+Manager اشار هگري به عامل است كه
براي كنترل عامل از آن استفاده مي نمايد.
From گر هاي را كه عامل قبل از حركت در آنجا قرار دارد
برم يگرداند.
FromLink آخرين اتصالي را كه عامل در آخرين حركت خود طي
كرده است برم يگرداند.
getContextInfo . اطلاعاتي را كه عامل در بردارد برمي گرداند
getNode() گر هاي را كه ه ماكنون عامل بر روي آن قرار دارد
برم يگرداند.
Go . عامل را به گره ديگري حركت مي دهد
Id . شناسه يكّه عامل را برم يگرداند
Initialize براي مقداردهي اوليه عامل Alchemi+ توسط
استفاده م يشود.
Replicate(GNode)
نسخ هاي از عامل جاري مي سازد (با وضعيت مشابه) و
آن را به مقصدي كه توسط شيءاي از كلاس
مشخص م يشود حركت م يدهد. GNode
Start عامل فعاليت اصلي خود را از اين متد آغاز م يكند.كد
محتوي برنامه كاربر در اين متد قرار مي گيرد.
Terminate . عامل جاري را از بين م يبرد
به صورت زير تعريف م يشود:
public interface IAgent: MarshalByRefObject {
public void Go (GNode dest) {…}
public void Go (GNodeCollection dests) {…}
}
GAgent 2-2-3 كلاس
را پياد هسازي كرده و متدهاي متعددي IAgent اين كلاس، واسط
از اعضاء اين getContextInfo() را فراهم مي آورد. متد Go() علاوه بر
كلاس، اطلاعاتي در مورد محتوياتي كه در حال اجراي آنها م يباشد، در
GAgent اختيار م يگذارد. در جدول 2 فهرستي از متدهاي مهم كلاس
ارائه شده است.
ContextInfo 3-2-3 كلاس
از اين كلاس، هر عامل براي دسترسي به منابعي از ماشين كه اين
عامل بر روي آن اجرا م يشود استفاده م ينمايد. اين منابع، شامل اشياء
متعلق به سيستم م يباشند كه ميزبان مي خواهد آنها را در اختيار عامل
getThreadIdentifier() سيار بگذارد. در حال حاضر، در اين مقاله متد
براي اين كلاس پياد هسازي شده است. اين متد شناسه نخي را كه در حال
اجراي عامل م يباشد برم يگرداند.
4-2-3 محل قرارگيري كد كاربر
مشتق شده است، GAgent كد كاربر بايستي در كلاسي كه از كلاس
نوشته شود. در اين كلاس م يتوان متدهاي ديگري نيز تعريف و
آغاز م يشود و void Start() پياد هسازي نمود. اجراي عامل از متد
بنابراين كد اجرايي كاربر بايستي در اين متد قرار گيرد. كدي كه در اين
كلاس پدر) به منظور ) GAgent متد نوشته مي شود، از متدهاي كلاس
نوشتن الگوريت مهاي موازي عام لگرا استفاده م يكند. همچنين در اين
public void sample (int x) {
int y;
// blocks of statements
BC1
BC2
}
.(sample) شكل 1: ساختار ساده يك متد
[Serializable]
protected class _sample: MarshalbyRefObject {
int x, y, progCounter=0; Object trgt;
void setPCForMove() {…}
void run() {…}
Try {…
this.request_read();
if ((progCounter==0)) {
progCounter+=1; BC1 }
this.read_accomplished();
this.request_read();
if ((progCounter==1)) {
progCounter+=1; BC2 }
this.read_accomplished(); }
catch(Exception e) {…}}…
}
.sample شكل 2: كلاس توليدشده از متد
كلاس بايستي متد سازنده 1 نيز تعريف گردد. فراخواني اين كلاس و
م يباشد. Alchemi مقداردهي اوليه آن، مانند ديگر برنامه هاي
5-2-3 ترجمه متدها
پي شپردازشگر براي هر متد عامل، يك كلاس كه اشياء آن،
ركوردهاي فعا لسازي آن متد را ارائه م يدهند، توليد م ينمايد. كلاس
ركورد فعال سازي هر متد، به صورت زير كلاسي از كلاس
كه براي اجراي كد بر روي مقصد راه دور ) MarshalByRefObject
را به صورتي كه در شكل 1 sample الزامي است) تعريف م يشود. تابع
و شمارنده برنامه، y متغير محلي ، x آمده است، در نظر بگيريد. پارامتر
خواهند بود. وجود متدي مانند _sample فيلدهايي از كلاس
به منظور تعليق اجرا و حركت دادن يك نخ، در setPCforMove()
كلاس توليدشده الزامي است. اين متد شمارنده برنامه جاري را ذخيره
كرده و سپس مقدار 1- را به آن م يدهد. اين كار به منظور اطمينان از
اينكه هيچ دستوري قبل از حركت عامل ناتمام باقي نمانده است، صورت
sample() شامل نگارش ترجم هشده بدنه تابع run() م يپذيرد. متد
خواهد بود. در اين تابع، كدي كه شمارنده برنامه را مي افزايد و نيز كدي
پس از حركت از وضعيت قبلي اجرا گردد قرار run() كه اجازه م يدهد تابع
دارد. هر نخ براي از بي نبردن مشكلات همگا مسازي، قبل و بعد از اجراي
هر عبارت به ترتيب قفلي را تقاضا و آزاد م يكند. اين كار توسط توابع
انجام م يگردد. كلاس read_accomplished() و request_read()
به صورت شكل 2 است. sample() ركورد فعا لسازي توليدشده از تابع
1. Constructor
www.SID.ir
dibaketab.com
نشريه مهندسي برق و مهندسي كامپيوتر ايران، سال 5، شماره 2، تابستان 1386
74
شكل 3: مسئله ضرب ماتريس ها: مثالي از الگوريتم هاي محاسبات عددي.
جدول 3: مشخصات محيط مورد استفاده در بررسي كارآيي الگوريت مها.
MPICH MPICH-G2 Alchemi+
8 پردازشگرها ×P4 2/4 GHz 1×P4 2/4 GHz 8×P4 2/4 GHz
Windows XP
Redhat Linux
9/0
Redhat Linux
9/0 سيست م عامل
.NET
Framework
Globus
ميا نافزار OS Kernel Toolkit 3/2
3 اصلاحات تكميلي -3
علاوه بر تغييرات ذكرشده در قسمت هاي قبلي، تغييرات زيادي در
به منظور تطبيق آن با مدل Alchemi اغلب كلاس هاي سيستم
برنام هنويسي موازي مبتني بر عامل هاي سيار صورت گرفته است. از جمله
،GThread ،GNode اين تغييرات م يتوان به اصلاحات در كلا سهاي
اشاره نمود. GLink و نيز تعريف كلاس GManager و GApplication
-4 ارزيابي كارآيي
پس از اصلاحات انجام شده و افزودن كلاس هايي كه برنام هنويسي
ميسر م ينمايند، به منظور بررسي كارآيي اين Alchemi عام لگرا را در
مجموع هاي از نقاط" و Convex Hull سيستم، دو الگوريتم "يافتن
(Alchemi+) "ضرب ماتريس ها" به صورت عام لگرا روي اين سيستم
پياد هسازي شده است. اين دو الگوريتم با استفاده از انتقال پيام بر روي دو
بر روي MPI برنام هنويسي مبتني بر ) MPICH-G و 2 MPICH محيط
گريد گلوباس) نيز پياد هسازي شده است. سپس نتايج به دست آمده از
با نتايج به دست آمده Alchemi+ اجراي اين الگوريت مها بر روي محيط
مقايسه شده است. MPICH-G و 2 MPICH از اجراي آنها بر روي
محيط اجراي الگوريت مها در جدول 3 ارائه گشته است. در ادامه، نحوه
پياد هسازي اين دو الگوريتم و بررسي كارآيي آ نها به تفكيك خواهد آمد.
1 ضرب ماتري سها -4
الگوريتم ضرب ماتري سها، يكي از الگوريت مهاي پركاربرد در محاسبات
عددي م يباشد، به رو شهاي مختلفي در محي طهاي توزي عشده قابل
پياد هسازي م يباشد. يكي از رو شهاي ضرب ماتري سها، به صورت
چرخشي بلوكي م يباشد. شكل 3 نحوه انجام اين الگوريتم را نمايش
نوشته Alchemi+API م يدهد. در شب هكد اين الگوريتم كه با استفاده از
شده و مبتني بر عام لهاي سيار م يباشد شكل 4، وجود يك شبكه منطقي
از كامپيوترها بر روي گريد مفروض در نظر گرفته شده است. عاملي كه در
منتشر slave قرار دارد، خود را بر روي تمامي گر ههاي master گره
.(9- م ينمايد (خط 8
matrix_mult(m) {
master=this.getContextInfo();
procs=m*m;
for (k=0; k<m; k++) {
sync=0; /*go to all slave nodes*/
for (i=0; i<GNodeCollection.getNodeCount(); i++)
this.Replicate(GNodeCollection.Item(i));
if (node.j==(node.i+k)%m) {
//multicast A to all nodes in the row
this.A=copy(this.getNode().A);
for (i=0; i<GNodeCollection.getNodeCount(); i++)
if (GNodeCollection.Item(i).getName().equals("row")
this.Replicate(GNodeCollection.Item(i));
} this.Terminate();
multiply(); //Cij=Aij*Bij
try { //barrier synchronization
GMonitor.Enter(sync);
sync++;
if (sync!=proc) GMonitor.Wait(sync);
else GMonitor.PalseAll(sync);
}
finally {
sync=0;
GMonitor.Exit(sync); }
this.B=copy(this.getNode().B);
//rotate B to column i-1
this.Go(this.FromLink("-column"));
this.getNode().B=copy(this.B);
try { //barrier synchronization
GMonitor.Enter(sync);
sync++;
if (sync!=proc) GMonitor.Wait(sync);
else GMonitor.PalseAll(sync);
}
finally {
sync=0;
GMonitor.Exit(sync);
}
}
}
.Alchemi+ شكل 4: حل مسئله ضرب ماتريس ها در سيستم
A عام لهايي كه بر روي قطر قرار دارند، به همراه قسمتي از ماتريس
در آن سطر حركت slave كه در اختيار آنها م يباشد، به ديگر گره هاي
را محاسبه كرده و A×B 16 ) آنگاه كليه عام لها - م يكنند (خط 10
27 ). عام لها سپس، - سپس فرآيند همگا مسازي انجام م يشود (خط 17
31 ) و - كه در اختيار دارند دوران داده (خط 28 B قسمتي از ماتريس
.(41- مجدداً همگا مسازي انجام م يگردد (خط 32
نمودارهاي كارآيي حاصل از اجراي اين الگوريتم بر روي سه محيطي
كه در جدول 3 برشمرده شده اند، در شكل 5- الف و 5- ب به ترتيب به
[180,180]×[ 160,160 ] و [ 180,180 ]×[ ازاي ضرب ماتري سهاي [ 160,160
نمايش داده شد هاند.
www.SID.ir
dibaketab.com
مافي و دلداري: برنام هنويسي موازي مبتني بر عامل هاي سيار بر روي گريد
75
جدول 4: زمان اجراي الگوريتم ضرب ماتري سها در سه محيط.
[160,160]×[ الف: [ 160,160
تعداد بستر اجرا MPICH MPICH-G2 Alchemi+
پردازشگرها
1 49/655 75/351 56/504
2 33/752 47/492 40/698
3 21/764 31/712 28/537
4 17/311 24/892 24/267
6 14/203 18/802 20/914
8 11/683 15/896 19/800
[180,180]×[ ب: [ 180,180
تعداد بستر اجرا MPICH MPICH-G2 Alchemi+
پردازشگرها
1 76/380 103/064 89/737
2 52/158 73/736 65/421
3 39/119 54/609 48/000
4 29/035 40/286 36/050
6 20/689 28/119 27/140
8 17/100 21/407 24/412
نتايج به دست آمده از اين آزمايش ها در جدول 4 نمايش داده شده
است. واحد زمان اجراي برنام هها ميل يثانيه م يباشد.
Alchemi+ دليل اينكه كارآيي الگوريتمي كه با استفاده از سيستم
نوشته شده است، با افزايش تعداد پردازشگرها كاهش مي يابد و نسبت به
ضعي فتر عمل م يكند، MPICH-G و 2 MPICH برنامه اجراشده بر روي
اين است كه با افزايش تعداد پردازشگرها بلوك هايي كه در هر پردازشگر
در هر تكرار محاسبه م يشوند، كوچ كتر شده و در نتيجه نسبت ارتباطات
به محاسبات افزايش مي يابد و نيز به علت سرباري كه اين سيستم در
زمان ارتباطات بر داده واقعي اضافه م يكند كه مجموع سربارهاي تحميلي
م يباشد، سرعت اجراي برنامه Alchemi+ و نهايتاً Alchemi ،.NET
اجرا MPICH كاهش م ييابد، در صورتي كه برنام هاي كه بر روي
م يشود، با كمترين سربار ممكن اجرا م يشود.
هما نطوري كه شكل 5- ب نشان م يدهد با افزايش ابعاد ماتريس
بهبود يافته و زمان اجراي آن به Alchemi+ كارآيي الگوريتم در سيستم
نزديك م يشود. مزيت عمده MPI زمان اجراي اين الگوريتم در محيط
اين سيستم اين است كه امكان اجراي موازي بر مبناي عام لها يك
الگوريتم را بر روي يك گريد كه به صورت جغرافيايي پراكنده است
فراهم م ينمايد.
در حقيقت سربارهاي اضافه شده به سيستم و در نتيجه افزايش زمان
اجراي الگوريتم، هزين هاي است كه كاربر در اِزاي وسي عترشدن دامنه
اجراي برنام هاش و امكان اجراي آن بر روي شبكه بزرگي كه مي تواند از
هاي متعددي ساخته شده باشد، م يپردازد. البته به دليل اينكه LAN
انجام شده تنها بر روي يك كامپيوتر MPICH-G آزمايشي كه بر روي 2
صورت گرفته و نتايج اين آزمايش به منظور مقايسه با ديگر آزمايش ها
را نسبت به Alchemi+ تسطيح شد هاند، نم يتوان كارآيي ضعي فتر
مورد اطمينان قرار داد. در حالت كلي، به دليل اينكه ،MPICH-G2
بسترهاي گريد، مدعي استفاده از منابع ب يكار كامپيوترهايي كه از لحاظ
هاي مختلفي قرار دارند، م يباشند، اجراي LAN جغرافيايي پراكنده و در
برنام ههايي بر روي گريد كه مؤلفه هاي آنها با يكديگر ارتباطات پرحجمي
دارند از كارآيي خوبي برخوردار نيست و منطقي به نظر نم يرسد.
[160,160]*[ الف: [ 160,160
0
10
20
30
40
50
60
70
80
0 1 2 3 4 5 6 7 8 9
تعداد پردازشگرها
(ms) زمان اجرا
MPICH MPICH-G2 Alchemi+
(الف)
[180,180]*[ ب: [ 180,180
0
20
40
60
80
100
120
0 1 2 3 4 5 6 7 8 9
تعداد پردازشگرها
(ms) زمان اجرا
MPICH MPICH-G2 Alchemi+
(ب)
شكل 5: نمودار كارآيي سه محيط در اجراي الگوريتم ضرب ماتري سها با ابعاد (الف)
.[180× 160] و (ب) [ 180 ×160]
مثالي از الگوريتم هاي تقسيم و حل. :Convex Hull شكل 6: مسئله
مجموع هاي از نقاط Convex Hull 2 يافتن -4
مجموعه اي از نقاط، كه از نوع Convex Hull الگوريتم يافتن
الگوريت مهاي تقسيم و حل به شمار م يرود، نيازمند ساخت درخت جستجو
به گون هاي پويا مي باشد. نگارش داد هها بر روي اين درخت، از نكات مهم
در حل اين مسئله م يباشد. هما نطور كه در شكل 6 ديده م يشود، برنامه
به نحوي كه هر زيرمجموعه در [n نقاط را به دو زيرمجموعه با اندازه [ 2
هر يك Convex Hull يك طرف خط قرار گيرند، تقسيم م يكند. سپس
از مجموع هها، به صورت بازگشتي با همين روش محاسبه مي شود.
با يكديگر (Backtracking) ح لهاي جزئي در هر سطح در فاز برگشت
ادغام م يشوند. آسا نترين راه براي پياد هسازي الگوريتم فوق به صورت
سِري، استفاده از توابع بازگشتي در ساخت و جم عآوري نتايج از درخت
م يباشد. در نگارش موازي اين الگوريتم، عمل بازگشت 1 به صورت ساخت
1. Recursion
www.SID.ir
dibaketab.com
نشريه مهندسي برق و مهندسي كامپيوتر ايران، سال 5، شماره 2، تابستان 1386
76
1. convex_hull(points)
2. {
3. for (i=0; i<max_level; i++) {
4. this.Replicate(new GLink("right"));
5. this.Replicate(new GLink("left"));
6. mid_pt=top_pt+(tail_pt-top_pt)/2;
7. if (this.FromLink().getName==''left")
8. tail_pt=mid_pt-1;
9. if (this.FromLink().getName==''right")
10. top_pt=mid_pt-1;
11. }
12. my_pt=convex(top_pt, tail_pt);
13. for (i=max_level; i>0; i--) {
14. this.Go(this.From());
15. if (other_pt==NULL) {
16. other_pt=my_pt;
17. this.Terminate();
18. } else
19. my_pt=merge(my_pt, other_pt);
20. }
21. }
.Alchemi+ در سيستم Convex Hull شكل 7: حل مسئله
در سه محيط. CONVEX HULL جدول 5: زمان اجراي الگوريتم
N = الف: 30
تعداد بستر اجرا MPICH MPICH-G2 Alchemi+
پردازشگرها
1 0/360 0/462 0/377
2 0/258 0/297 0/271
3 0/192 0/238 0/212
4 0/159 0/207 0/190
6 0/134 178/0 0/151
8 0/087 0/155 0/113
N = ب: 50
تعداد بستر اجرا MPICH MPICH-G2 Alchemi+
پردازشگرها
1 2/055 2/363 2/158
2 1/104 1/430 1/270
3 0/651 0/984 0/810
4 0/462 0/787 0/693
6 0/344 0/551 0/481
8 0/238 0/503 0/385
فرآيندهاي جديد و انتقال داده به آن ها صورت م يپذيرد.
و با بهر هگيري Alchemi+API در شكل 7 برنام هاي كه با استفاده از
از عام لهاي سيار و خواص آن ها، براي حل اين مسئله (با حذف
قسم تهاي غير ضروري)، ارائه شده است.
نمودارهاي كارآيي حاصل از اجراي اين الگوريتم بر روي سه محيطي
كه در جدول 3 برشمرده شد هاند، در شكل 8- الف و 8- ب به ترتيب به
ازاي 30 و 50 نقطه نمايش داده شده اند.
همچنين نتايج به دست آمده از اين آزماي شها در جدول 5 نمايش داده
شده است.
N= الف: 30
0.000
0.050
0.100
0.150
0.200
0.250
0.300
0.350
0.400
0.450
0.500
0 1 2 3 4 5 6 7 8 9
تعداد پردازشگرها
(ms) زمان اجرا
MPICH MPICH-G2 Alchemi+
(الف)
N= ب: 50
0.000
0.500
1.000
1.500
2.000
2.500
0 1 2 3 4 5 6 7 8 9
تعداد پردازشگرها
(ms) زمان اجرا
MPICH MPICH-G2 Alchemi+
(ب)
N = الف) 30 ) Convex Hull شكل 8: نمودار كارآيي سه محيط در اجراي الگوريتم
. N = و (ب) 50
در اين الگوريتم حجم داده هاي منتق لشده توسط عام لها كمتر از
الگوريتم ضرب ماتري سها م يباشد. هما نطور كه شكل 8 نشان م يدهد
به كارآيي اين Alchemi+ در سيستم Convex Hull كارآيي الگوريتم
نزدي كتر و از كارآيي اين الگوريتم در MPICH الگوريتم در سيستم
Alchemi+ بهتر م يباشد. كارآيي پايي نتر سيستم MPICH-G سيستم 2
را مانند مثال گذشته مي توان در سربار چارچوب MPICH نسبت به
نسبت به هسته لينوكس و سربارهاي افزون تري كه به جهت .NET
اضافه شده است، Alchemi امكان قابليت تحرك قوي به سيستم
جستجو كرد. بهين هسازي تبديل كد قوي به كد ضعيف و تقسيم داده
مناس بتر ميان عامل ها م يتوانند به عنوان را هح لهايي براي اين مشكل
در نظر گرفته شوند.
-5 نتيج هگيري و كارهاي آينده
كه محيط برنام هنويسي موازي مبتني Alchemi+ در اين مقاله سيستم
بر عام لهاي سيار را بر روي گريد فراهم آورده است، ارائه گشته است.
اين كار با افزوده شدن دستورات پاي هاي در برنام هنويسي موازي با استفاده
كه فراه مكننده بستر گريد بر روي Alchemi از عام لها، بر روي سيستم
كامپيوترهاي شخصي م يباشد، ميسر گشته است. از مه مترين اصلاحات
كه برنام ههاي كاربر GAgent در اين سيستم، م يتوان به افزودن كلاس
با ار ثبري از آن ساخته مي شوند و شامل دستورات راهبري و ديگر
كه GMonitor ملزومات برنام هنويسي عام لگرا مي باشد و نيز كلاس
امكان ارتباط ميان ن خهاي در حال اجرا بر روي گريد را فراهم م يسازد
ممكن نبوده است)، اشاره داشت. در ادامه با اجراي دو Alchemi (كه در
مجموع هاي از نقاط كه Convex hull الگوريتم ضرب ماتري سها و يافتن
به ترتيب به الگوريت مهاي محاسبات عددي و "تقسيم و حل" تعلق دارند،
كارآيي اين سيستم مورد بررسي قرار گرفته است. با بررسي نتايج م يتوان
MPICH-G ادعا نمود كه سيستم فوق در اغلب موارد بهتر از سيستم 2
م يتوان به MPICH عمل كرده است. از دلايل ضعف سيستم نسبت به
www.SID.ir
dibaketab.com
مافي و دلداري: برنام هنويسي موازي مبتني بر عامل هاي سيار بر روي گريد
77
سربار بيشتر چارچوب .NET علاوه . سبت به هسته لينوكس اشاره داشت ن
بر سربار فوق، سربار ديگري نيز به منظور تبديل كد با قابليت تحرك قوي
قابل اجرا باشد، به برنامه هاي Alchemi به كدي با تحرك ضعيف، كه در
افزوده مي شود. همچنين بهره سرعت 1 انداز هگير يشده براي Alchemi+
دو الگوريتم فوق داراي رشد تقريباً خطي و قابل قبولي م يباشد.
از نوآوري هاي اين مقاله مي توان به ايجاد قابليت تحرك قوي در
و نيز ارائه مدل برنام هنويسي موازي مبتني بر عامل هاي .NET چارچوب
سيار بر روي بستر گريد اشاره نمود. گريد توسع هيافته در اين تحقيق
نا مگذاري شده است كه يك گريد بر پايه عام لها م يباشد. Alchemi+
از ديگر نوآوري هاي اين مقاله، مقايس هاي است كه ميان سه محيط
مطر حشده صورت پذيرفته است. بنا بر اطلاعات نگارندگان تاكنون
مقايس هاي با اين خصوصيات در تحقيق ديگري انجام نشده است.
از مجموعه كارهاي قابل انجام در راستاي اين مقاله در آينده، مي توان
و BSP Tree3 ،FFT از اجراي الگوريت مهاي پركاربرد ديگري از قبيل 2
نام برد. Alchemi+ بر روي سيستم CSG4
به منظور افزايش كارآيي سيستم م يتوان اصلاحاتي در نحوه
همگا مسازي عام لهاي سيار انجام داد.
همچنين مي توان كليه الگوريت مها را از نظر طبيعتشان به چند دسته
تقسيم نمود و براي هر دسته از الگوريت مها يك اسكلت بر روي سيستم
به صورت كارا پياد هسازي نمود. در اين صورت م يتوان Alchemi+
كارآيي اجراي الگوريت مها را به نحو چشمگيري بر روي سيستم
بهبود بخشيد. Alc

نظرات شما عزیزان:

نام :

آدرس ایمیل:

وب سایت/بلاگ :

متن پیام:

نظر خصوصی

 کد را وارد نمایید:

 

 

 

عکس شما

آپلود عکس دلخواه: